// https://www.lintcode.com/problem/rogue-knight-sven/description

class Solution {
public:
    /**
     * @param n: the max identifier of planet.
     * @param m: gold coins that Sven has.
     * @param limit: the max difference.
     * @param cost: the number of gold coins that reaching the planet j through the portal costs.
     * @return: return the number of ways he can reach the planet n through the portal.
     */
    // long long getNumberOfWays(int n, int m, int limit, vector<int> &cost) {
    //     // vector<vector<long long>> rec(n, vector<long long>(m + 1));
    //     vector<vector<long long>> rec(n + 1, vector<long long>(m + 1)); //星球是从0到n
    //     rec[0][m] = 1;
    //     for (int i = 0; i < m; ++i)
    //     {
    //         rec[0][i] = 0;
    //     }
    //     for (int i = 1; i < n + 1; ++i)
    //     {
    //         for (int j = 0; j < m + 1 - cost[i]; ++j) //或者这些边界条件放到里面去判断，容易想一些
    //         {
    //             //在星球i，有j元钱（交了cost[i]之后）
    //             for (int k = max(i - limit, 0); k < i; ++k)
    //             {
    //                 rec[i][j] += rec[k][j + cost[i]];
    //             }
    //         }
    //     }
    //     long long res = 0;
    //     for (int i = 0; i < m + 1; ++i)
    //     {
    //         res += rec[n][i];
    //     }
    //     return res;
    // }
    
    // 优化，部分和数组，O(mn)
    long long getNumberOfWays(int n, int m, int limit, vector<int> &cost) {
        vector<vector<long long>> rec(n + 1, vector<long long>(m + 1));
        vector<vector<long long>> sum(n + 1, vector<long long>(m + 1));

        rec[0][m] = 1;
        sum[0][m] = 1;
        for (int i = 0; i < m; ++i)
        {
            rec[0][i] = 0;
            sum[0][i] = 0;
        }
        for (int i = 1; i < n + 1; ++i)
        {
            // 注意出口，需要把sum都赋值才行
            for (int j = 0; j < m + 1; ++j) 
            {
                sum[i][j] = sum[i - 1][j];
                if (j < m + 1 - cost[i])
                {
                    //同样的，rec[i][j]要赋值，不能直接减sum[max(i - limit, 0)][j + cost[i]]，不然减sum[0]那个是多减
                    rec[i][j] = sum[i - 1][j + cost[i]];
                    if (i - limit - 1 >= 0)
                        rec[i][j] -= sum[i - limit - 1][j + cost[i]];
                    sum[i][j] += rec[i][j];
                }
            }
        }
        long long res = 0;
        for (int i = 0; i < m + 1; ++i)
        {
            res += rec[n][i];
        }
        return res;
    }
};